package com.learn.finished;
/*大餐 是指 恰好包含两道不同餐品 的一餐，其美味程度之和等于 2 的幂。

你可以搭配 任意 两道餐品做一顿大餐。

给你一个整数数组 deliciousness ，其中 deliciousness[i] 是第 i​​​​​​​​​​​​​​ 道餐品的美味程度，返回你可以用数组中的餐品做出的不同 大餐 的数量。结果需要对 109 + 7 取余。

注意，只要餐品下标不同，就可以认为是不同的餐品，即便它们的美味程度相同。

示例 1：

输入：deliciousness = [1,3,5,7,9]
输出：4
解释：大餐的美味程度组合为 (1,3) 、(1,7) 、(3,5) 和 (7,9) 。
它们各自的美味程度之和分别为 4 、8 、8 和 16 ，都是 2 的幂。
示例 2：

输入：deliciousness = [1,1,1,3,3,3,7]
输出：15
解释：大餐的美味程度组合为 3 种 (1,1) ，9 种 (1,3) ，和 3 种 (1,7) 。

提示：

1 <= deliciousness.length <= 105
0 <= deliciousness[i] <= 220
*
* */
/** 是否可以将数组化成树，然后通过求每一节点的和*/

import java.util.*;

public class num_1711 {
    public static void main(String[] args) {

        //int[] a={1,1,1,3,3,3,7};//[1,2,2,3,4]
               //0,1,2,3,4  a.length =5
        //对其进行排列组合，分别有(0,1-4),(1,2-4),(2,3-4),(3,4)
        //用双指针，则，i=0-length-1 , j=i+1-length
        //通过组合，有1+2,1+2,1+3,1+4,2+2,2+3,2+4,2+3,2+4,3+4共10种变化
                //  3   3   4   5   4   5   6   5   6   7
        int[] b={149,107,1,63,0,1,6867,1325,5611,2581,39,89,46,18,12,20,22,234};
        Arrays.sort(b);
                //0  1  1  12  18  20  22  39  46  63  89  107  149  234  1325  2581  5611  6867
//        for (int i = 0; i < a.length-1; i++) {
//            for (int j = i+1; j < a.length; j++) {
//                list.add(a[i]+a[j]);
//            }
//        }
        //System.out.println(countPairs(a));
        System.out.println(countPairs(b));
    }

    private static int countPairs(int[] deliciousness) {
        int mod = (int)1e9+7;
        int max = 1 << 22;//10000000000000000000000
        //System.out.println(max);
        int a=1;
        System.out.println(Integer.toBinaryString(a<<=1));
        System.out.println(Integer.toBinaryString(max));
            Map<Integer, Integer> map = new HashMap<>();
            int deliciousNums = 0;
            //取数
            for (int x : deliciousness) {
                //i<<=1 二进制数i在右边+0  1->10...->100...
                for (int i = 1; i < max; i <<= 1) {
                    //2的幂次数-数组的元素
                    int key = i - x;
                    //如果key存在于map中
                    if (map.containsKey(key)) {
                        //map.get是输入key，得到value
                        //则将value加进deliciousNums中
                        deliciousNums += map.get(key);
                        if (deliciousNums >= mod){
                            deliciousNums -= mod;
                        }
                    }
                }
                //如果key x 存在于map中，则返回x对应的value，如果不存在，则返回0
                //然后将x作为key，x对应的value或者1存储到map中
                map.put(x, map.getOrDefault(x, 0) + 1);
            }
            return deliciousNums;
        }

    public static int oldCountPairs(int[] deliciousness) {
        int deliciousNums=0;
//        int maxSum=0;
        ArrayList<Integer> evenArrays = new ArrayList<>();
        Arrays.sort(deliciousness);
        for (int i : deliciousness) {
            System.out.print(i+ "  ");

        }
        System.out.println();
        //是否可以用双指针
        //所有组合已经存储到list中
        for (int i = 0; i < deliciousness.length-1; i++) {
            for (int j = i+1; j < deliciousness.length; j++) {
                //排除奇数
                System.out.println("测试："+(deliciousness[i]+deliciousness[j]));;
                if ((deliciousness[i]+deliciousness[j])%2==0){
                    evenArrays.add(deliciousness[i]+deliciousness[j]);
                }
            }
        }
        Collections.sort(evenArrays);
        //System.out.println("偶数数组"+evenArrays);
        System.out.println(Math.sqrt(evenArrays.get(evenArrays.size()-1))+1);
        for (int i = 0; i < Math.sqrt(evenArrays.get(evenArrays.size()-1))+1; i++) {
            for (Integer evenArray : evenArrays) {
                if (evenArray==Math.pow(2,i)){
                    System.out.println("2次的"+i+"幂："+evenArray);
                    deliciousNums+=1;
                }
            }
        }

        System.out.println("complete");
        return deliciousNums;
    }
}
